# 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
#
#  示例 1：
# 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
# 输出：4
#
#  示例 2：
# 输入：matrix = [["0","1"],["1","0"]]
# 输出：1
#
#  示例 3：
# 输入：matrix = [["0"]]
# 输出：0
from typing import List


class Solution:
    def maximalSquare1(self, matrix: List[List[str]]) -> int:
        """
        动态规划
        dp[i][j]表示以 (i, j)为右下角的最大矩形的边长
        以(i,j)为右下角的最大的正方形边长,取决于它的左边(dp[i - 1, j]),上面(dp[i, j - 1]）,以及左上(dp[i - 1, j - 1])的值
        :param matrix:
        :return:
        """
        rows, columns, maxSide = len(matrix), len(matrix[0]), 0
        dp = [[0] * columns for _ in range(rows)]  # dp[i][j]表示以 (i, j)为右下角的最大矩形的边长
        for i in range(rows):
            if matrix[i][0] == '1':
                dp[i][0] = 1
                maxSide = max(maxSide, dp[i][0])
        for j in range(columns):
            if matrix[0][j] == '1':
                dp[0][j] = 1
                maxSide = max(maxSide, dp[0][j])
        for i in range(1, rows):
            for j in range(1, columns):
                if matrix[i][j] == '1':
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
                    maxSide = max(maxSide, dp[i][j])
        return maxSide * maxSide

    def maximalSquare(self, matrix: List[List[str]]) -> int:
        return self.maximalSquare1(matrix)


if __name__ == '__main__':
    matrix = [["1", "0", "1", "0", "0"],
              ["1", "0", "1", "1", "1"],
              ["1", "1", "1", "1", "1"],
              ["1", "0", "0", "1", "0"]]
    matrix = [["0", "1"], ["1", "0"]]
    print(Solution().maximalSquare(matrix))
